#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.4节：变换字符串(语法规则替换)
#          将源字符串src通过一系列规则rule变换成目标字符串tgt, 变换步骤不超过10
#  此算法为广度优先算法，数据结构关键部分是一个双向队列 que

import numpy as np
from pprint import pprint
from collections import deque, namedtuple

item = namedtuple('item', ['s', 'count'])

def gen(src, tgt, rule):
    que = deque()
    que.append(item(src, 0))
    found = False
    while que:
        current = que.popleft()
        if current.s == tgt :
            found = True
            break

        if current.count > 10: continue

        for r in rule.keys():
            k = 0
            while k >= 0:
                k = current.s.find(r, k) # 如果没有找到，返回-1
                if k >= 0 :
                    nxt_s = current.s[:k] + current.s[k:].replace(r, rule[r], 1)
                    if len(nxt_s) <= 20:
                        que.append(item(nxt_s, current.count+1))
                    k +=1
    if found :
        print current
    else :
        print 'No Answer!'

if __name__ == '__main__':
    src, tgt = 'a', 'aaaa'
    rule = {'a': 'a1122334455',
            '1122' : 'a',
            '334455' : '23a',
            '23' : 'a',
            }
    gen(src, tgt, rule)

    src, tgt = 'abcd', 'xyz'
    rule = {'abc': 'xu',
            'ud': 'y',
            'y': 'yz',
            }
    gen(src, tgt, rule)
    
